package it.luigiarpino.kernighanLin.bipartition;

import java.util.HashSet;
import java.util.Set;

public class LKphase1 
{

	private int[][] W;
	
	private Set<Integer> setA;
	private Set<Integer> setB;
	
	private Set<Integer> setApasso;
	private Set<Integer> setBpasso;
	
	private int[] D;
	
	private int Ap;
	private int Bp;
	
	
	private int[] Gi;
	private int G;
	private int[] setX;
	private int[] setY;
	
	private int[]  gain;
	private int[]  Ai;
	private int[]  Bi;
	
	
	
	public LKphase1(int[][] matrix, int[] partizioneA, int[] partizioneB)
	{
		// gestisco il caso singolare n=2
		if (matrix.length==2)
		{
			this.setX=new int[1];
			this.setX[0]=partizioneA[0];
			this.setY=new int[1];
			this.setY[0]=partizioneB[0];
			this.G=0;
			return;
		}
		// inizializzazione
		this.W=matrix;
		D=new int[matrix.length];
		int n = matrix.length/2;
		this.gain=new int[n];
		this.Ai=new int[n];
		this.Bi=new int[n];
		setA=new HashSet<Integer>();
		setB=new HashSet<Integer>();
		setApasso=new HashSet<Integer>();
		setBpasso=new HashSet<Integer>();
		//
		int[] partA=getNewVettore(partizioneA);
		int[] partB=getNewVettore(partizioneB);
		//calcolaRandomPartition();
		for (int i=0; i<partA.length; i++)
		{
			this.setA.add(new Integer(partA[i]));
			this.setApasso.add(new Integer(partA[i]));
			this.setB.add(new Integer(partB[i]));
			this.setBpasso.add(new Integer(partB[i]));
		}
		int passo=0;
		// calcolo D
		calcolaDiniziale();
		int[] result=scegliApBp();
		this.Ap=result[0];
		this.Ai[passo]=result[0];
		this.Bp=result[1];
		this.Bi[passo]=result[1];
		this.gain[passo]=result[2];
		// memorizzo i valori
		setApasso.remove(new Integer(Ap));
		setBpasso.remove(new Integer(Bp));
		
		passo++;
	    do {
	    	calcolaD();
			result=scegliApBp();
			Ap=result[0];
			this.Ai[passo]=result[0];
			Bp=result[1];
			Bi[passo]=result[1];
			this.gain[passo]=result[2];;
			setApasso.remove(new Integer(Ap));
			setBpasso.remove(new Integer(Bp));
			passo++;
	    } while (passo < matrix.length/2);
	    // calcolo Gi
	    Gi=new int[matrix.length/2];
	    for(int k=0; k< (matrix.length/2) ; k++)
	    {
	    	Gi[k] = 0;
	    	for (int  i=0 ; i<=k ;i++)
	    	{
	    		Gi[k] += gain[i];
	    	}
	    }
	    // scelgo la iMax che massimizza Gi;
	    int iMax=-1;
	    int max=0;
	    boolean isFirstCycle=true;
	    for (int j=0;j<matrix.length/2 ;j++)
	    {
	    	if ( isFirstCycle || Gi[j]>max)
	    	{
	    		iMax=j;
	    		max=Gi[j];
	    		isFirstCycle=false;
	    	}
	    }
	    // memorizzo i risultati trovati
	    this.G=max;
	    this.setX=new int[iMax+1];
	    this.setY=new int[iMax+1];
	    for(int i=0; i< iMax+1 ; i++)
	    {
	    	this.setX[i]=this.Ai[i];
	    	this.setY[i]=this.Bi[i];
	    }
	}
	
	
	private int[] getNewVettore(int[] vett)
	{
		int[] result=new int[vett.length];
		for (int i=0;i<vett.length;i++)
		{
			result[i]=vett[i];
		}
		return result;
	}
	
	/**
	 * Restituisce il valore di G
	 * @return
	 */
	public int getGain()
	{
		return this.G;
	}
	
	/**
	 * Restituisce il sottoinsieme X della partizione A
	 * da spostare nella partizione B
	 * @return
	 */
	public int[] getSetX()
	{
		return this.setX; 
	}
	
	/**
	 * Restituisce il sottoinsieme Y della partizione B
	 * da spostare nella partizione A
	 * @return
	 */
	public int[] getSetY()
	{
		return this.setY; 
	}
	
	
	private void calcolaD()
	{
		for(Object objectA: setApasso.toArray() )
		{
			int x=((Integer)objectA).intValue();
			D[x] = D[x] + 2*W[x][Ap] - 2*W[x][Bp];
		}
		for(Object objectB: setBpasso.toArray() )
		{
			int y=((Integer)objectB).intValue();
			D[y] = D[y] + 2*W[y][Bp] - 2*W[y][Ap];
		}
	}
	
	/*
	private int[] scegliApBp()
	{
		// Euristica a tempo lineare
		int Ap=-1;
		int Bp=-1;
		int maxGain=0;
		boolean isFirstCycle=true;
		for(Object objectA: setApasso.toArray() )
		{
			int a = ((Integer)objectA).intValue();
			if (isFirstCycle )
			{
				Ap=a;
				isFirstCycle=false;
			}
			else
			{
				if (D[a]>D[Ap])
				{
					Ap=a;
				}
			}
		}
		isFirstCycle=true;
		for(Object objectB: setBpasso.toArray() )
		{
			int b = ((Integer)objectB).intValue();
			if(isFirstCycle)
			{
				Bp=b;
				isFirstCycle=false;
			}
			else
			{
				if (D[b]>D[Bp])
				{
					Bp=b;
				}
			}
		}
		maxGain=D[Ap] + D[Bp]-( 2 * W[Ap][Bp] );
		return new int[]{Ap,Bp, maxGain};
	}
	*/
	
	
	private int[] scegliApBp()
	{
		int Ap=-1;
		int Bp=-1;
		int maxGain=0;
		boolean isFirstCycle=true;
		
		for(Object objectA: setApasso.toArray() )
		{
			int a = ((Integer)objectA).intValue();
			for(Object objectB: setBpasso.toArray() )
			{
				int b = ((Integer)objectB).intValue();
				int gain = D[a] + D[b]-( 2 * W[a][b] );
				if (isFirstCycle || gain>maxGain)
				{
					Ap=a;
					Bp=b;
					maxGain=gain;
					isFirstCycle=false;
				}
			}
		}
		return new int[]{Ap,Bp, maxGain};
	}
	
	
	
	
	
	private void calcolaDiniziale()
	{
		// Calcolo i costi esterni
		int[] E = new int[W.length];
		for(Object objectA: setA.toArray() )
		{
			int a =((Integer)objectA).intValue();
			E[a]=0;
			for(Object objectY: setB.toArray() )
			{
				int y =((Integer)objectY).intValue();
				E[a] += W[a][y];
			}
			//
		}
		for(Object objectB: setB.toArray() )
		{
			int b =((Integer)objectB).intValue();
			E[b]=0;
			for(Object objectY: setA.toArray() )
			{
				int y =((Integer)objectY).intValue();
				E[b] += W[b][y];
			}
			//System.out.println("E["+a+"]="+E[a]);
		}
		// Cacolo i costi interni
		int[] I = new int[W.length];
		for(Object objectA: setA.toArray() )
		{
			int a =((Integer)objectA).intValue();
			I[a]=0;
			for(Object objectX: setA.toArray() )
			{
				int x =((Integer)objectX).intValue();
				I[a] += W[a][x];
			}
		}
		for(Object objectB: setB.toArray() )
		{
			int b =((Integer)objectB).intValue();
			I[b]=0;
			for(Object objectX: setB.toArray() )
			{
				int x =((Integer)objectX).intValue();
				I[b] += W[b][x];
			}
		}
		//calcolo D
		for (int i=0 ; i<E.length ; i++)
		{
			D[i] = E[i] - I[i];
		}
	}
	
	public static void main(String[] args)
	{
		int[][] matrix={
			    //   0  1 
					{0, 1},// 0
					{1, 0},// 1
			};
		
		LKphase1 lk=new LKphase1(matrix, new int[]{0}, new int[]{1});
		int[] parX=lk.getSetX();
		int[] parY=lk.getSetY();
		int gain = lk.getGain();
		System.out.println();
		System.out.println("Gain="+gain);
		System.out.println();
		System.out.println("\nset X");
		for(int i=0; i< parX.length ; i++)
	    {
			System.out.print(" "+parX[i]);
	    }
		System.out.println("\nset Y");
		for(int i=0; i< parY.length ; i++)
	    {
			System.out.print(" "+parY[i]);
	    }
	}
}
